As a conventional method of configuring an image processing apparatus which losslessly encodes and decodes an image, a predictive coding-based method has been proposed. A predictive encoding apparatus generally has a string conversion unit which converts image data into a prediction error by predictive transform. The predictive encoding apparatus also has an entropy encoding unit which converts the prediction error output from the string conversion unit into encoded data of less redundancy by using entropy encoding such as Huffman encoding.
JPEG (ITU-T T.81|ISO/IEC 10918-1) recommended as a still image coding scheme of an international standard by ISO and ITU-T defines a lossless coding scheme in which a lossless process is based on predictive coding. This lossless coding scheme will be called a JPEG lossless coding mode. In the JPEG lossless coding mode, seven prediction equations are defined as a method of predicting the value of a pixel of interest from neighboring pixels, and the prediction method can be selected in accordance with an image.
FIG. 2 is a block diagram showing a conventional image processing apparatus. FIG. 2 shows an example of the apparatus which losslessly compresses an image in the above-described JPEG lossless coding mode. In FIG. 2, reference numeral 201 denotes a buffer; 202, a component value prediction unit; 203, a subtracter; 204, a Huffman table memory; 205, a prediction error encoding unit; 209, a code string formation unit; and 206, 207, and 208, signal lines.
The Huffman table memory 204 stores a Huffman table for use in the prediction error encoding unit 205. Assume that the Huffman table memory 204 stores a Huffman table shown in FIG. 6.
The flow of a process when a conventional image processing apparatus encodes a color image whose R. G, and B components each are expressed by 8 bits will be explained with reference to FIG. 2.
A prediction selection signal m for selecting a prediction method for use in the component value prediction unit 202 is input from the signal line 208. The prediction selection signal m takes an integer value of 0 to 7, and the respective values correspond to different prediction equations. FIG. 4 shows the correspondence between the prediction equation for use and the prediction selection signal m. When the prediction selection signal m is 0, no prediction equation is defined. This means that each component is directly encoded without performing any predictive transform. Symbols p, a, b, and c in FIG. 4 will be explained below.
Image data are sequentially input from the signal line 206. The image data input order is the raster scan order, and component data of each pixel are input in the order of R, G, and B. The R, G, and B components are defined as component numbers of 0, 1, and 2, respectively. The upper left corner of an image is defined as coordinates (0,0), and the value of the component number C of a pixel at the horizontal right pixel position x and vertical lower pixel position y is represented by P(x,y,C). For example, when a pixel at the position (x,y)=(3,4) has (R,G,B)=(255,128,0), P(3,4,0)=255, P(3,4,1)=128, and P(3,4,2)=0.
The buffer 201 stores image data of two lines that are input from the signal line 206.
When the component value x of the pixel of interest=P(x,y,C), the component value prediction unit 202 extracts, from the buffer 201, the value a of the same component of an immediately preceding pixel=P(x−1,y,C), the value b of the same component of a pixel before one line=P(x,y−1,C),and the value c of the same component of an obliquely upper left pixel=P(x−1,y−1,C). The component value prediction unit 202 generates a predicted value p from the extracted values a, b, and c in accordance with the prediction scheme selection signal m. FIG. 3 shows the positional relationship between a, b, c, and the component value x of the pixel of interest. When the pixel of interest is positioned on the uppermost line of the image, the preceding value a is used as the predicted value p. When the pixel of interest is positioned at the left end of the image, the value b before one line is used as the predicted value p. For the first pixel (pixel at the left end of the uppermost line) of the image, “128” is used as the predicted value p. In the image data input order, which has been described above, the positions of the pixels a, b, and c are encoded-pixel positions.
The subtracter 203 calculates the difference value between the predicted value p and the component value x to be encoded, and outputs it as a prediction error e.
The prediction error encoding unit 205 classifies prediction errors e input from the subtracter 203 into a plurality of groups, and generates a group number SSSS and overhead bits of a bit length defined for each group. FIG. 5 shows the relationship between the prediction error e and the group number SSSS. The overhead bits are Information for specifying a prediction error in the group, and the bit length is given by the group number SSSS. Note that the bit length is exceptionally 0 for SSSS=16 (when the precision of each component is 8 bits, SSSS=16 is not generated). If the prediction error e is positive, the lower SSSS bits of the prediction error e become overhead bits; if the prediction error e is negative, the lower SSSS bits of e−1 become overhead bits. The MSB (Most Significant Bit) of overhead bits is 1 for a positive prediction error e and 0 for a negative prediction error e. In an encoding process, encoded data corresponding to the group number SSSS is output by referring to the Huffman table stored in the memory 204. When SSSS is neither 0 nor 16, overhead bits of a bit length defied by the group number are output.
The code string formation unit 209 forms a code string of a format complying with the JPEG standard from encoded data output from the prediction error encoding unit 205, and additional information (e.g., the prediction selection signal m input via the signal line 208, the numbers of horizontal and vertical pixels of an image, the number of components which form a pixel, and the precision of each component). The code string formation unit 209 outputs the code string to the signal line 207.
When the image processing apparatus using the conventional scheme described above encodes image data (e.g., a CG image or an image of limited colors) having a biased frequency distribution of the luminance, the generation frequency of the prediction error after the above-mentioned string conversion is also biased to several specific prediction error values.
In this case, a prediction error which is rarely or not generated sometimes exists though a short code length is assigned as a code length by entropy encoding, resulting in low compression ratio.
To solve this problem, there has conventionally been known a method of determining whether the generation frequency distribution of the prediction error is discrete, changing encoded data corresponding to a prediction error in accordance with the determination result, and performing entropy encoding (e.g., Japanese Patent Laid-Open No. 10-004551; to be referred to as reference 1 hereinafter). There is also proposed a method of determining whether an image to be encoded is made up of discrete pixel values, and correcting a predicted value in accordance with the determination result (e.g. Japanese Patent Laid-Open No. 10-004557; to be referred to as reference 2 hereinafter). Note that the contents of references 1 and 2 are combined as U.S. Pat. No. 6,028,963. There is also known a method of encoding matching information with neighboring pixels in encoding each pixel (e.g., Japanese Patent Laid-Open No. 10-336458 (U.S. Pat. No. 6,212,234); to be referred to as reference 3 hereinafter). There is also known a method of switching between a plurality of predictive encoding methods (e.g., Japanese Patent Laid-Open No. 9-224253 (U.S. Pat. No. 5,828,789); to be referred to as reference 4 hereinafter).
In reference 1 or 2, the generation status of the component value of each pixel or that of the prediction error must be grasped, increasing the process load. When each component is predictively encoded using a block code such as a Huffman code, at least 1 bit is necessary for one component. High compression ratios can be expected from the predictive coding technique for a natural image (e.g., an image obtained by sensing the real world with a digital camera). However, there is room for improvement in coding efficiency for image data of low entropy such as a text, line art, or CG image. This also applies to references 3 and 4.